typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;//标准化书写，结构体成员变量前边下划线
	int _top;//栈顶下标
	int _capacity;//容量
}Stack;
void StackInit(Stack* pst)//初始化栈
{
	assert(pst);
	pst->_a = (STDataType*)malloc(sizeof(STDataType) * 4);
	pst->_top = 0;
	pst->_capacity = 4;
}
void StackDestroy(Stack* pst)//销毁栈
{
	assert(pst);
	free(pst->_a);
	pst->_a = NULL;
	pst->_top = pst->_capacity = 0;
}
void StackPush(Stack* pst, STDataType x)//入栈
{
	assert(pst);
	if (pst->_top == pst->_capacity)
	{
		//增容
		pst->_capacity *= 2;
		STDataType* tmp = (STDataType*)realloc(pst->_a, sizeof(STDataType) * pst->_capacity);
		if (tmp == NULL)
		{
			printf("增容失败\n");
			exit(-1);
		}
		else
		{
			pst->_a = tmp;
		}
	}
	pst->_a[pst->_top] = x;
	pst->_top++;
}
void StackPop(Stack* pst)//出栈
{
	assert(pst);
	assert(pst->_top > 0);
	--pst->_top;
}
int StackSize(Stack* pst)//1、为了保持接口的一致性 2、结构体若太大，传指针好些
{
	assert(pst);
	return pst->_top;
}
int StackEmpty(Stack* pst)//返回1则表示栈空，返回0表示栈非空
{
	assert(pst);
	return pst->_top == 0 ? 1 : 0;
}
STDataType StackTop(Stack* pst)//获取栈顶的元素
{
	assert(pst);
	assert(pst->_top > 0);
	return pst->_a[pst->_top - 1];
}

typedef struct {
	Stack _popST;
	Stack _pushST;

} MyQueue;


MyQueue* myQueueCreate()
{
	MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&(q->_popST));
	StackInit(&q->_pushST);
	return q;
}

void myQueuePush(MyQueue* obj, int x) {
	StackPush(&obj->_pushST, x);

}
int myQueuePeek(MyQueue* obj) {
	if (!StackEmpty(&obj->_popST))
	{
		return StackTop(&obj->_popST);
	}
	else {
		while (StackEmpty(&obj->_pushST))
		{
			StackPush(&obj->_popST, StackTop(&obj->_pushST));
			StackPop(&obj->_pushST);
		}
		return StackTop(&obj->_popST);
	}
}
int myQueuePop(MyQueue* obj) {
	int front = myQueuePeek(&obj);
	StackPop(&obj->_popST);
	return front;
}



bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(&obj->_popST) && StackEmpty(&obj->_pushST);

}

void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->_popST);
	StackDestroy(&obj->_pushST);
	free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/